#include <iostream>
#include <stack>
#include <queue>
namespace YX
{
    // 两个栈实现队列
    template<typename T>
    class Queue
    {
        private:
            std::stack<T> _popStack; 
            std::stack<T> _pushStack;
    
            void CheckPopStackEmpty()
            {
                if(_popStack.empty())
                {
                    while(!_pushStack.empty())
                    {
                        _popStack.push(_pushStack.top());
                        _pushStack.pop();
                    }
                }
            }

        public:

            void push(const T& val)
            {
                _pushStack.push(val);
            }


            void pop()
            {
                if(empty())
                    return;

                CheckPopStackEmpty();
                _popStack.pop();

            }

            T front()
            {

                if(empty())
                    return T();

                CheckPopStackEmpty();
    
                return _popStack.top();
            }

            T back()
            {
                if(empty())
                    return T();

                return _pushStack.top();
            }

            bool empty()
            {
                return _pushStack.empty()&&_popStack.empty();
            }
            
            std::size_t size()
            {
                return _pushStack.size()+_popStack.size();
            }
    };

    // 用栈将队列中所有的元素逆置
    template<typename T>
    void ReverseQueue(std::queue<T>& q)
    {
        std::stack<T> st;

        while(!q.empty())
        {
            st.push(q.front());
            q.pop();
        }

        while(!st.empty())
        {
            q.push(st.top());
            st.pop();
        }
    }

    // 循环队列
    template<class T>
    class CQueue 
    {
        private:
            std::vector<T> _v;
            int _rear;
            int _size;
        public:
            CQueue(size_t n)
                :_v(n)
                ,_rear(0)
                ,_size(0)
            {

            }

            void push(const T& val)
            {
                if(full())
                    return;

                _v[_rear]=val;

                _size++;

                _rear=(_rear+1)%_v.size();
            }

            void pop()
            {
                if(empty())
                    return;
                _size--;
            }

            bool empty()
            {
                int head=(_rear-_size+_v.size())%_v.size();
                return head==_rear;
            }

            bool full()
            {
                return _size==_v.size();
            }

            int size()
            {
                return _size;
            }

            T front()
            {
                int head=(_rear-_size+_v.size())%_v.size();
                return _v[head];
            }

            T back()
            {
                int rearPrev=(_rear-1+_v.size())%_v.size();

                return _v[rearPrev];
            }

    };

};

int main(int argc,char* argv[],char* env[])
{

    YX::CQueue<int> cq(10);

    cq.push(1);
    cq.push(2);
    cq.push(3);
    cq.push(4);
    cq.push(5);

    while(!cq.empty())
    {
        std::printf("%d ",cq.front());
        cq.pop();
    }
    std::cout<<std::endl;
    
    //std::queue<int> q;
    //q.push(1);
    //q.push(2);
    //q.push(3);
    //q.push(4);
    //q.push(5);

    //YX::ReverseQueue(q);

    //while(!q.empty())
    //{
    //    std::printf("%d ",q.front());
    //    q.pop();
    //}
    //std::cout<<std::endl;


//    YX::Queue<int> q;
//
//    q.push(1);
//    q.push(2);
//    q.push(3);
//    q.push(4);
//    q.push(5);
//    q.push(6);
//
//    while(!q.empty())
//    {
//        std::printf("%d ",q.front());
//        q.pop();
//    }
//
//
    return 0;
}

